#ifndef __NQUEENS_H__
#define __NQUEENS_H__
#include <vector>
#include <string>
using namespace std;
/*
* leetcode 51 N皇后
* 
* n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击
* 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案
* 
* 输入：n = 4
* 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
* 
*/

/*
* 对于 N皇后 问题, 可以使用回溯法穷举来解决
* 树形结构如下:
*						棋盘 n * n
* 取格子: (0, 0)		(0, 1)	....
* (1, 0) (1, 1)...	...
* 
* 如上述的树形图, 对于一个 n * n 的棋盘, 第一层取第一行的格子, 第二层取第二行...
* 每次通过判断是否符合要求 (皇后不互相攻击), 来完成穷举
*/
bool IsNQueens(vector<string>& chessboard, int row, int col);

void BackTrackingNQueens(vector<string>& chessboard, vector<vector<string>>& results, int row = 0) {
	if (row == chessboard.size()) {
		results.push_back(chessboard);
		return;
	}

	// col == row
	// 取该 row 的每一 col
	for (int col = 0; col < chessboard.size(); col++) {
		if (!IsNQueens(chessboard, row, col))
			continue;

		chessboard[row][col] = 'Q';
		//进入下一 row
		BackTrackingNQueens(chessboard, results, row + 1);
		chessboard[row][col] = '.';
	}
}

bool IsNQueens(vector<string>& chessboard, int row, int col) {
	//横向
	for (int c = 0; c < col; c++)
		if (chessboard[row][c] == 'Q')
			return false;

	//纵向
	for (int r = 0; r < row; r++)
		if (chessboard[r][col] == 'Q')
			return false;

	//斜向
	for (int r = row - 1, c = col - 1; r >= 0 && c >= 0; r--, c--)	//45
		if (chessboard[r][c] == 'Q')
			return false;

	for (int r = row - 1, c = col + 1; r >= 0 && c < chessboard.size(); r--, c++) //135
		if (chessboard[r][c] == 'Q')
			return false;

	return true;
}

#endif // !__NQUEENS_H__

